#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    void dfs(int step, int start, vector<int>& nums, vector<int> &tuple, vector<vector<int>> &ans){
        if(step > nums.size()) return;
        ans.emplace_back(tuple);
        int n = nums.size();
        for(int i=start; i<n; ++i){
            tuple.push_back(nums[i]);
            dfs(step+1, i+1, nums, tuple, ans);
            tuple.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> tuple;
        dfs(0, 0, nums, tuple, ans);
        return ans;
    }
};